from typing import List


class Solution:
    def maximalSqure(self, matrix: List[List[int]]) -> int:
        if len(matrix) == 0:
            return 0

        n_rows = len(matrix)
        n_cols = len(matrix[0])
        psum = [[0 for _ in range(n_cols+1)] for _ in range(n_rows+1)]
        for row in range(n_rows):
            for col in range(n_cols):
                psum[row+1][col+1] = psum[row][col+1] + psum[row+1][col] - psum[row][col] + matrix[row][col]

        max_size = 0
        for row1 in range(n_rows):
            for col1 in range(n_cols):
                for size in range(max_size + 1, min(n_rows - row1 + 1, n_cols - col1 + 1)):
                    row2 = row1 + size - 1
                    col2 = col1 + size - 1
                    if psum[row2 + 1][col2 + 1] + psum[row1][col1] - psum[row2+1][col1] - psum[row1][col2+1] == (row2 - row1 + 1) * (col2 - col1 + 1):
                        max_size = size
                    else:
                        break

        return max_size * max_size


def brutal_solve(matrix):
    import numpy as np
    if len(matrix) == 0:
        return 0
    matrix = np.asarray(matrix, dtype=np.int32)
    n_rows = len(matrix)
    if n_rows == 0:
        return 0
    n_cols = len(matrix[0])

    result = 0
    for row0 in range(n_rows):
        for row1 in range(row0, n_rows):
            for col0 in range(n_cols):
                for col1 in range(col0, n_cols):
                    if (row1-row0) != (col1-col0):
                        continue
                    area = (row1-row0+1) * (col1-col0+1)
                    if area > result and matrix[row0: row1+1, col0: col1+1].sum() == (row1-row0+1) * (col1-col0+1):
                        result = area
    return result


print(Solution().maximalSqure([[1, 1], [1, 1]]))
print(Solution().maximalSqure([[0, 1, 1], [1, 1, 1]]))
print(Solution().maximalSqure([[0]]))
print(Solution().maximalSqure([[0, 0, 0], [0, 1, 1], [0, 1, 1]]))
print(Solution().maximalSqure([[0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 1], [0, 1, 1, 1]]))


def test():
    # 对拍
    import random
    for i in range(10000):
        n_rows = random.randint(0, 6)
        n_cols = random.randint(1, 6)
        matrix = [['' for _ in range(n_cols)] for _ in range(n_rows)]
        for row in range(n_rows):
            for col in range(n_cols):
                v = random.randint(0, 3)
                matrix[row][col] = int(bool(v))
        res1 = Solution().maximalSqure(matrix)
        res2 = brutal_solve(matrix)
        if res1 != res2:
            print(matrix, res1, res2)
test()


def test2():
    # 性能测试
    import time
    t1 = time.time()
    import random
    for i in range(10):
        n_rows = random.randint(150, 200)
        n_cols = random.randint(150, 200)
        matrix = [['' for _ in range(n_cols)] for _ in range(n_rows)]
        for row in range(n_rows):
            for col in range(n_cols):
                v = random.randint(0, 3)
                matrix[row][col] = int(bool(v))
        res1 = Solution().maximalSqure(matrix)
    t2 = time.time()
    print('%.3f seconds for 10 cases' % (t2 - t1))

test2()
